\documentclass[a4paper,10pt]{article}

%linguagem
\usepackage[brazil]{babel}
%encodificação
\usepackage[utf8]{inputenc}
%biblioteca de matemática
\usepackage{amssymb,amsmath}
%pacote para codigo fonte
\usepackage{listings}
%figuras
\usepackage{graphicx}
%cores
\usepackage{color}
%paragrafo no inicio da secao
\usepackage{indentfirst}
%url
\usepackage{framed, url}
\usepackage{fancyvrb}

%define a cor "claro"
\definecolor{claro}{gray}{0.96}

%configurações do fancy verbatim
\fvset{frame=single, xleftmargin=-80pt, xrightmargin=-80pt}
%configurações do listings
\lstset{frame=trBL, numbers=left, xleftmargin=0pt, xrightmargin=0pt,
breaklines=true, backgroundcolor=\color{claro}}

\begin{document}

\input{./titulo.tex}
\tableofcontents
\pagebreak

\section{Introdução}
O compilador é o programa responsável por transformar um código-fonte de uma
linguagem de programação em outra linguagem, geralmente um código binário, ou
executável. O processo de compilação é feito através de várias etapas, como
mostrado na figura \ref{fig:fases}. 

\begin{figure}[h] 
\centering
\includegraphics[scale=0.6]{imagens/fases.png} 
\label{fig:fases} 
\caption{Fases do processo de compilação} 
\end{figure}

Depois da geração de código pelo compilador, um interpretador é usado para
executar as instruções contidas neste código e finalmente realizar as tarefas
descritas no código-fonte feito pelo programador.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/interpretador.png}
\label{fig:interpretador}
\caption{Interpretador}
\end{figure}

Esta etapa da construção do compilador consiste na especificação e
implementação do tradutor de código intermediário para código MEPA. O interpretador
da linguagem MEPA foi implementado no segundo trabalho prático.

\section{Código Intermediário}

O código de três endereços é composto por uma sequência de instruções
envolvendo operações binárias ou unárias e uma atribuição. O nome ``três endereços''
está associado à especificação, em uma instrução, de no máximo três variáveis: duas
para os operadores binários e uma para o resultado. Assim, expressões envolvendo
diversas operações são decompostas nesse código em uma série de instruções,
eventualmente com a utilização de variáveis temporárias introduzidas na tradução.
Dessa forma, obtém-se um código mais próximo da estrutura da linguagem assembly
e, consequentemente, de mais fácil conversão para a linguagem-alvo.

Uma possível especificação de uma linguagem de três endereços envolve quatro
tipos básicos de instruções: expressões com atribuição, desvios, invocação de rotinas e
acesso indexado e indireto.

Instruções de atribuição são aquelas nas quais o resultado de uma operação é
armazenado na variável especificada à esquerda do operador de atribuição, aqui
denotado por :=. Há três formas para esse tipo de instrução. Na primeira, a variável
recebe o resultado de uma operação binária:
                
\colorbox{claro}{x := y op z}

O resultado pode ser também obtido a partir da aplicação de um operador
unário:

\colorbox{claro}{x := op y}

Na terceira forma, pode ocorrer uma simples cópia de valores de uma variável
para outra:
          
\colorbox{claro}{x := y}

Por exemplo, a expressão em C

\colorbox{claro}{a = b + c * d}

seria traduzida nesse formato para as instruções:
\begin{verbatim}
_t1 := c * d
a := b + _t1
\end{verbatim}

As instruções de desvio podem assumir duas formas básicas. Uma instrução de
desvio incondicional tem o formato

\colorbox{claro}{goto L}

onde L é um rótulo simbólico que identifica uma linha do código. A outra forma
de desvio é o desvio condicional, com o formato
       
\colorbox{claro}{if x opr y goto L}

onde opr é um operador relacional de comparação e L é o rótulo da linha que
deve ser executada se o resultado da aplicação do operador relacional for verdadeiro;
caso contrário, a linha seguinte é executada.

Por exemplo, a seguinte iteração em C
\begin{verbatim}
while (i++ <= k)
  x[i] = 0;
  x[0] = 0;
\end{verbatim}

poderia ser traduzida para

\begin{verbatim}
_L1: if i > k goto _L2
i := i + 1
x[i] := 0
goto _L1
_L2: x[0] := 0
\end{verbatim}

A invocação de rotinas ocorre em duas etapas. Inicialmente, os argumentos do
procedimento são ``registrados'' com a instrução param; após a definição dos
argumentos, a instrução call completa a invocação da rotina. A instrução return indica
o fim de execução de uma rotina. Opcionalmente, esta instrução pode especificar um
valor de retorno, que pode ser atribuído na linguagem intermediária a uma variável
como resultado de call.

Por exemplo, considere a chamada de uma função f que recebe três argumentos
e retorna um valor:

\colorbox{claro}{f(a, b, c);}

Neste exemplo em C, esse valor de retorno não é utilizado. De qualquer modo, a
expressão acima seria traduzida para

\begin{verbatim}
param a
param b
param c
_t1 := call f,3
\end{verbatim}

onde o número após a vírgula indica o número de argumentos utilizados pelo
procedimento f. Com o uso desse argumento adicional é possível expressar sem
dificuldades as chamadas aninhadas de procedimentos.

O último tipo de instrução para códigos de três endereços refere-se aos modos
de endereçamento indexado e indireto. Para atribuições indexadas, as duas formas
básicas são

\colorbox{claro}{x := y[i]}

\colorbox{claro}{x[i] := y}

As atribuições associadas ao modo indireto permitem a manipulação de
endereços e seus conteúdos. As instruções em formato intermediário também utilizam
um formato próximo àquele da linguagem C:

\colorbox{claro}{x := \&y}

\colorbox{claro}{w := *x}

\colorbox{claro}{*x := z}

A representação interna das instruções em códigos de três endereços dá-se na
forma de armazenamento em tabelas com quatro ou três colunas. Na abordagem que
utiliza quádruplas (as tabelas com quatro colunas), cada instrução é representada por
uma linha na tabela com a especificação do operador, do primeiro argumento, do
segundo argumento e do resultado. Por exemplo, a tradução da expressão a=b+c*d;
resultaria no seguinte trecho da tabela:

\begin{center}
\begin{tabular}{| l | l | l | l |}
\hline
operador & arg1 & arg2 & resultado \\ \hline
* & c & d & \_t1 \\ \hline
+ & b & \_t1 & a \\ \hline
\end{tabular}
\end{center}

Para algumas instruções, como aquelas envolvendo operadores unários ou
desvio incondicional, algumas das colunas estariam vazias.

Na outra forma de representação, por triplas, evita a necessidade de manter
nomes de variáveis temporárias ao fazer referência às linhas da própria tabela no lugar
dos argumentos. Nesse caso, apenas três colunas são necessárias, uma vez que o
resultado está sempre implicitamente associado à linha da tabela. No mesmo exemplo
apresentado para a representação interna por quádruplas, a representação por triplas
seria:

\begin{center}
\begin{tabular}{| l | l | l |}
\hline
operador & arg1 & arg2 \\ \hline
* & c & d \\ \hline
+ & b & (1) \\ \hline
\end{tabular}
\end{center}

\section{Desenvolvimento}

O trabalho foi desenvolvido utilizando a linguagem ``Java''. Foram implementados
módulos para a tabela de símbolos, quádruplas e para o tradutor. Os detalhes
estão apresentados a seguir:

\subsection{TAD Tabela de Símbolos}

A tabela de símbolos usada foi a mesma implementada no primeiro trabalho
prático. 


\subsection{TAD Quadrupla} 
O TAD quádrupla é um TAD muito simples que possui um campo String com
o operador e três campos inteiros para os operandos. As operações são simplesmente
operações que retornam os valores desses campos. Elas são respectivamente:
getOperador(), getOperando1(), getOperando2() e getOperando3().

\subsection{Tradução das Quádruplas}
A seguir explicaremos detalhadamente como é feita a tradução de cada um dos
tipos de quádruplas possíveis para o código MEPA. Vamos utilizar uma notação 
comum para elas, onde os pares x1,y1, x2,y2 e w,z
correspondem a níveis e deslocamentos respectivamente dos 3 operandos de uma
quádrupla.

As possíveis quádruplas são:

\begin{center}
\begin{tabular}{| l | l | l | l |}
\hline
:= & b & 0 & a \\ \hline
-un & b & 0 & a \\ \hline
not & b & 0 & a \\ \hline
op & a & b & c \\ \hline
read & 0 & 0 & a \\ \hline
write & 0 & 0 & a \\ \hline
if & a & 0 & L \\ \hline
goto & 0 & 0 & L \\ \hline
call & k & 0 & L \\ \hline
param & a & 0 & 0 \\ \hline
entr & a & 0 & 0 \\ \hline
rtpr & a & 0 & 0 \\ \hline
amem & a & 0 & 0 \\ \hline
dmem & a & 0 & 0 \\ \hline
inicio & 0 & 0 & 0 \\ \hline
fim & 0 & 0 & 0 \\ \hline

\end{tabular}
\end{center}



\subsubsection{Atribuição de cópia}
As quádruplas de atribuição de cópia são quádruplas referentes à operação
\colorbox{claro}{a := b}

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
CRVL x,y ou CRCT const
ARMZ w,z 
\end{verbatim}

\subsubsection{Atribuição com Menos Unário}
    A atribuição com menos unário é idêntido à atribuição de cópia, porém o valor
a ser copiado tem seu sinal invertido antes da atribuição.

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
CRVL x,y ou CRCT const
INVR
ARMZ w,z
\end{verbatim}

\subsubsection{Operação de Negação}
    A operação de negação recebe um valor inteiro referente a uma variável 
	booleana e inverte seu valor, armazenando o resultado em outra variável. Sua sintaxe
é \colorbox{claro}{a := not b}.

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
CRVL x,y ou CRCT const
NEGA
ARMZ w,z
\end{verbatim}

\subsubsection{Operações}
    As operações incluem todas as operações numéricas e também as operações
lógicas de relação. Elas possuem tratamento idêntico, diferindo apenas na instrução
 da operação MEPA referente à mesma operação em alto nível. São operações:
+, *, /, -, and, or, $>$, $>=$, $<$, $<=$,$ =$, $!=$. Sua sintaxe é
\colorbox{claro}{c := a op b}

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
CRVL x1,y1 ou CRCT const
CRVL x2,y2 ou CRCT const
OPERACAO MEPA
ARMZ w,z
\end{verbatim}

OPERACAO MEPA pode ser qualquer uma
das seguintes operações: SOMA, SUBT, MULT, DIVI, CONJ, DISJ, CMMA,
CMME, CMIG, CMDG, CMEG, CMAG.

\subsubsection{Leitura do Teclado}
    A instrução de leitura do teclado recebe um valor do teclado e o armazena na
variável passada. A sua sintaxe é \colorbox{claro}{read a}.

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
LEIT
ARMZ w,z
\end{verbatim}

\subsubsection{Escrita na Tela}
    A instrução de escrita na tela é semelhante à de leitura, porém ao invés de ler
um valor do teclado e armazenar em uma variável, ele lê um valor de uma variável
ou constante e imprime aquele valor na tela. Sua sintaxe é
\colorbox{claro}{write a}.

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
CRVL x,y ou CRCT const
IMPR
\end{verbatim}

\subsubsection{Desvios Condicionais}
    As operações de desvio condicionais foram escolhidas para serem independentes
das operações de comparação, uma vez que podemos tanto realizar um desvio em
uma variável já existente sem antes fazer a operação de comparação, quanto podemos
 querer realizar uma comparação e armazenar seu resultado em uma variável
sem realizar um desvio.
    Dessa forma, reduzimos o número de quádruplas de desvio condicional para
somente uma, com a sintaxe \colorbox{claro}{if not a goto L}, onde o not está explícito só para
destacar que o desvio é realizado caso ‘a’ seja falso, que é o mesmo que um valor
inteiro 0. 
    L é o número referente a uma quádrupla. Isso gera um problema, já que o endereço de uma 
	quádrupla não corresponde a um endereço MEPA proporcionalmente, já que existem
quádruplas que podem ser traduzidas em um número maior de instruções MEPAs
que as outras, como são as instruções de atribuição indexada.

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
CRVL x1,y1 ou CRCT const
DSVF endereço MEPA de L
\end{verbatim}

\subsubsection{Desvios Incondicionais}
    Os desvios incondicionais são bem parecidos com os desvios condicionais,
principalmente por ter o mesmo problema referente ao endereço MEPA da 
quádrupla de destino. Portanto usamos a mesma estratégia usada
no algoritmo do desvio condicional.

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
DSVS endereço MEPA de L
\end{verbatim}

\subsubsection{Chamada de Procedimento Comum}
    A chamada de procedimento comum é simplesmente um desvio para uma 
	quádrupla que inicia um procedimento. Por motivos de facilidade de implementação,
foi considerado que o tradutor passa quádruplas de entrada e saída do procedimento,
 assim esta quádrupla não passa de um desvio para uma outra. A sintaxe é
 \colorbox{claro}{call k L},
 onde ‘k’ é o nível no qual o procedimento foi declarado e ‘L’ é o endereço da
quádrupla que inicia o procedimento. Tal como os desvios, esse endereço de quádrupla
 precisa ser traduzido para um endereço coerente de uma instrução MEPA.


Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
CHPR endereço MEPA de L,k
\end{verbatim}

\subsubsection{Carregar Parâmetros Comuns}
    O carregamento de parâmetros comuns é relativamente simples, mas assim
como todas as variáveis, estão sujeitas ao problema de podermos estar passando
variáveis locais ou parâmetros para a próxima função, e variáveis locais devem ter
seu endereço empilhado enquanto que variáveis de parâmetro devem ter o valor
do endereço copiado para ser empilhado, uma vez que como todos os parâmetros
são feitos por referência.
    Essa instrução não tem uma sintaxe própria, ela é simplesmente a ocorrência
de um parâmetro de uma função.



Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
CRVL x1,y1
\end{verbatim}

\subsubsection{Entrada de Procedimento}
   Esta quádrupla correponde à entrada de um procedimento, e recebe como 
argumento um número absoluto que indica o nível do procedimento.
   Essa instrução não possui uma sintaxe de alto nível, uma vez que é gerada
sempre que um procedimento se inicia.


Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
ENTR a
\end{verbatim}

\subsubsection{Retornar de Procedimento}
    Esta quádrupla corresponde à saída de um procedimento, e recebe como 
argumento o número absoluto que indica quantos parâmetros devem ser desalocados
da pilha ao sair do procedimento, além de termos que seguir o endereço de retorno
do registro de ativação.
    Assim como a instrução de entrada, não há uma sintaxe de alto nível para essa
instrução



Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
RTPR a
\end{verbatim}

\subsubsection{Alocar Memória}
    Esta instrução terá que acompanhar um valor que não só contenha todos as
variáveis locais usadas no escopo quanto também todas as variáveis temporárias
criadas durante o processo de quebra das instruções em quádruplas. Sua sintaxe é
\colorbox{claro}{amem a}.

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
AMEM a
\end{verbatim}

\subsubsection{Desalocar Memória}
    Assim como a quádrupla de alocar memória, a quádrupla de desalocar
 memória deve vir acompanhada de um número absoluto que contenha a soma das
variáveis locais com as variáveis temporárias criadas durante o processo de quebra 
das instruções em quádruplas.    A sintaxe é \colorbox{claro}{dmem a}.


Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
DMEM a
\end{verbatim}

\subsubsection{Inicio de Programa}
   Para adicionar a funcionalidade de compilar mais de um programa por arquivo,
foi decidido que existiriam quádruplas para iniciar e terminar os programas. Essas
quádruplas são simplesmente substituídas por seus correspondentes, e não carregam nenhum operando.


Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
INPP
\end{verbatim}

\subsubsection{Fim de Programa}

Sua quádrupla gera o seguinte código MEPA:
\begin{verbatim}
PARA
\end{verbatim}


\section{Instruções para utilização}

\medskip
\colorbox{claro}{\$ java Teste} 
\medskip

\section{Testes}

Abaixo está a saída do tradutor para diferentes códigos intermediários.

\subsection{Teste 1}

Desvios.

Entrada:
\VerbatimInput{../testes/tabela1.txt}
\VerbatimInput{../testes/quad1.txt}

Saída:

\VerbatimInput{../testes/teste1.out}

\subsection{Teste 2}


Entrada:
\VerbatimInput{../testes/tabela2.txt}
\VerbatimInput{../testes/quad2.txt}

Saída:

\VerbatimInput{../testes/teste2.out}


\subsection{Teste 3}


Entrada:
\VerbatimInput{../testes/tabela3.txt}
\VerbatimInput{../testes/quad3.txt}

Saída:

\VerbatimInput{../testes/teste3.out}



\section{Conclusão}
		
O desenvolvimento deste trabalho possibilitou o aprendizado acerca do
funcionamento de um tradutor de código intermediário para a linguagem MEPA. 

\section{Código-fonte}

\subsection{Teste.java}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../src/Teste.java}

\subsection{Tabela.java}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../lib/Tabela.java}

\subsection{Quadrupla.java}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../lib/Quadrupla.java}

\subsection{Tradutor.java}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../lib/Tradutor.java}

\subsection{Simbolo.java}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../lib/Simbolo.java}


\clearpage
\begin{thebibliography}{99}
\bibitem{wiki} \url{en.wikipedia.org/wiki/Lex_(software)}
\bibitem{tut1} \url{http://dinosaur.compilertools.net/lex/index.html}
\bibitem{tut2} \url{http://ds9a.nl/lex-yacc/cvs/output/lexyacc.html}
\bibitem{tut3} \url{http://osr507doc.sco.com/en/tools/Lex_yacc.html}
\bibitem{mansic} \url{https://homepages.dcc.ufmg.br/~mariza/Cursos/CompiladoresI/Artigos/mansic.doc}
\bibitem{livro} Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, \emph{Compilers - Principles Techniques and Tools}, 2006
\end{thebibliography}

\end{document}
